package map.oj;

import java.util.*;
/**
 * 前K个高频单词
 */
public class Num692 {
    //把单词和对应的次数包装成类
    private static class WordNumber implements Comparable<WordNumber>{
        String word;
        int count;
        WordNumber(String word, int count){
            this.word = word;
            this.count = count;
        }
        @Override
        //传入可比较的能力，比较this和o
        public int compareTo(WordNumber o) {
            //次数出现多的在前面
            if(count > o.count){
                return -1;
            }else if(count < o.count){
                return 1;
            }else {
                //两个count相等就要再比word，因为要按照单词顺序
                return word.compareTo(o.word);
            }
        }
    }
    public List<String> topKFrequent(String[] words, int k) {
        //每个单词出现的次数          统计每个单词出现的次数
        Map<String, Integer> map = countNum(words);
        //一共有map.size()个单词
        WordNumber[] array = new WordNumber[map.size()];
        int index = 0;
        //遍历map，用Entry转成entrySet
        for (Map.Entry<String,Integer> entry : map.entrySet()){
            String word = entry.getKey();//单词
            int count = entry.getValue();//次数
            //把转化成set的一对组合创建为一个对象
            WordNumber w2c = new WordNumber(word, count);
            //保存在数组中
            array[index++] = w2c;
        }
        //对出现次数+字母顺序进行排序
        Arrays.sort(array);
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < k; i++){
            ans.add(array[i].word);
        }
        return ans;

    }
    //传入一个单词数组，返回一个键值对<单词，出现次数>
    private Map<String, Integer> countNum(String[] words) {
        Map<String, Integer> map = new TreeMap<>();
        //遍历单词，记录次数
        for (String word : words){
            int count = map.getOrDefault(word,0) + 1;
            map.put(word,count);
        }
        return map;
    }
}
